package com.sx.sx1.lintcode.day717;

import java.util.*;

public class LC1057 {

    static class Solution {
        /**
         * @param times: a 2D array
         * @param n: an integer
         * @param k: an integer
         * @return: how long will it take for all nodes to receive the signal
         */
        public int networkDelayTime(int[][] times, int n, int k) {
            //核心1：构建图
            /*
            首先，bfs也可以用来做有向图，边长不固定的最短路径
            这个题里面，关键是bfs要把所有的路径都走一遍，并记录到达当前点的最小值是什么。
            如果到达当前点的cost比之前记录的cost低，那么就再放到queue里面。这种方法叫什么pfsa之类的。
            反正记住一点，bfs继续走下去，值更小的时候更新值，并再放到queue里面。
            最后把所有的cost都看一遍，找到其中的最大值。
             */
            Map<Integer, Set<Node>> g  = new HashMap<>();
            for (int[] time : times) {
                int a =time[0];
                int b =time[1];
                int cost =time[2];
                if(!g.containsKey(a)){
                    g.put(a,new HashSet<>());
                }

                g.get(a).add(new Node(b,cost));
            }

            //BFS,推出结果
            Queue<Integer> q = new LinkedList<>();
            Map<Integer,Integer> distance = new HashMap<>();
            q.add(k);
            distance.put(k,0);
            while (!q.isEmpty()){
                int cur = q.poll();
                int dis = distance.get(cur);
                if(!g.containsKey(cur))
                    continue;

                for (Node next : g.get(cur)) {
                    if(!distance.containsKey(next.data) || next.dis+ dis< distance.get(next.data)){
                        distance.put(next.data,next.dis+dis);
                        q.add(next.data);
                    }
                }
            }

            if(distance.size()!=n) return -1;
            int ans=0;
            for (Integer dis : distance.values()) {
                ans=Math.max(ans,dis);
            }
            return ans;
        }

        static class Node{
            public int data;
            public int dis;
            public Node(int d,int di){
                data =d;
                dis=di;
            }
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
//        System.out.println(obj.networkDelayTime(new int[][]{{2,1,1},{2,3,1},{3,4,1}},4,2));
//        System.out.println(obj.networkDelayTime(new int[][]{{1,2,1}},2,1));
//        System.out.println(obj.networkDelayTime(new int[][]{{1,2,1}},2,2));
       // System.out.println(obj.networkDelayTime(new int[][]{{1,2,1},{2,3,7},{1,3,4},{2,1,2}},3,1));
        System.out.println(new Solution().networkDelayTime(new int[][]{{1,2,1},{2,3,7},{1,3,4},{2,1,2}},3,2));
        System.out.println(new Solution1().networkDelayTime(new int[][]{{1,2,1},{2,3,7},{1,3,4},{2,1,2}},3,2));
    }


    static class Solution1 {
        /**
         * @param times: a 2D array
         * @param n: an integer
         * @param k: an integer
         * @return: how long will it take for all nodes to receive the signal
         */
        public int networkDelayTime(int[][] times, int n, int k) {
            // SPFA
        /*
        首先，bfs也可以用来做有向图，边长不固定的最短路径
        这个题里面，关键是bfs要把所有的路径都走一遍，并记录到达当前点的最小值是什么。
        如果到达当前点的cost比之前记录的cost低，那么就再放到queue里面。这种方法叫什么pfsa之类的。
        反正记住一点，bfs继续走下去，值更小的时候更新值，并再放到queue里面。
        最后把所有的cost都看一遍，找到其中的最大值。
         */
            Map<Integer,Set<Info>> graph = new HashMap<>();
            for (int[] arr : times) {
                int a= arr[0],b=arr[1],c=arr[2];
                if(!graph.containsKey(a))
                    graph.put(a,new HashSet<>());
                graph.get(a).add(new Info(b,c));
            }

            Map<Integer,Integer> distances = new HashMap<>();
            Queue<Integer> queue = new LinkedList<>();
            queue.add(k);
            distances.put(k,0);

            while (!queue.isEmpty()){
                int cur= queue.poll();
                int curdis = distances.get(cur);
                if(!graph.containsKey(cur))
                    continue;

                for(Info next: graph.get(cur)){
                    if(!distances.containsKey(next.data) || next.dis+curdis < distances.get(next.data)){
                        distances.put(next.data,next.dis+curdis);
                        queue.add(next.data);
                    }
                }
            }

            if(distances.size()!=n)
                return -1;

            int ans =0;
            for(int dis: distances.values()){
                ans=Math.max(ans,dis);
            }
            return ans;
        }

        static class Info {
            int data;
            int dis;

            public Info(int d, int d1) {
                data = d;
                dis = d1;
            }
        }

    }
}

/*


[[1,2,1],[2,3,7],[1,3,4],[2,1,2]]
3
1
输出数据
11
期望答案
4



[[1,2,1],[2,3,7],[1,3,4],[2,1,2]]
3
2
输出数据
11
期望答案
6


[[1,2,1]]
2
2
输出数据
0
期望答案
-1
 */

/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有218条未读消息，请及时查看
1057 · 网络延迟时间
算法
中等
通过率
55%

题目
题解19
笔记
讨论29
排名
记录
描述
有 N个网络节点，从 1 到 N标记.

给定 times，一个旅行时间和有向边列表 times[i] = (u, v, w)，其中u 是起始点， v是目标点， w是一个信号从起始到目标点花费的时间。

现在，我们从一个特定节点 K发出信号，所有节点收到信号需要花费多长时间? 如果不可能，返回-1。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


1.N 是 [1, 100]内的整数.
2.K 位于 [1, N]范围内.
3. times 的长度在范围 [1, 6000] 内.
4. 所有边 times[i] = (u, v, w) 将会有 1 <= u, v <= N 以及1 <= w <= 100.

样例
样例 1:
	输入:  times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
	输出:  2

样例 2:
	输入: times = [[1,2,1]], N = 2, K = 1
	输出:  1

	解释:
	两条路选择最短的。

相关知识
学习《FLAG最新面试高频难题精讲》课程中的4.1ACM亚洲金牌选手精讲最短路（下）相关内容 ，了解更多相关知识！
标签
企业
Akuna Capital
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
已开启智能提示
发起考试
30 分 00 秒
1234567891011
}
控制台
历史提交

 */
